package Arrays;

/**
 * 作者:hfj
 * 功能:121.买股票的最佳时机
 * 日期: 2025/10/27 10:05
 */
public class MaxProfit {
    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfit(prices));
    }

    //超出时间,时间复杂度O(n方)
    public static int maxProfit1(int[] prices) {
        int res = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i+1; j < prices.length; j++) {
                if (prices[i] < prices[j] && (prices[j] - prices[i] > res)){
                    res = prices[j] - prices[i];
                }else {
                    continue;
                }
            }
        }
        return res;
    }

    //方法不对
    public static int maxProfit2(int[] prices) {
        int res = 0,index = 0,min = 999999999;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min){
                min = prices[i];
                index = i;
            }
        }
        for (int i = index+1; i < prices.length; i++) {
            if (prices[i] - prices[index] > res){
                res = prices[i] - prices[index];
            }
        }
        return res;
    }

    //DP动态规划思想
    public static int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int min = prices[0], max = 0;
        for(int i = 1; i < prices.length; i++) {
            max = Math.max(max, prices[i] - min);//计算最大利润
            min = Math.min(min, prices[i]);//更新当前最小值并记忆
        }
        return max;
    }
}
